/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 18, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a string s and a dictionary of words dict, add spaces in s
 *              to construct a sentence where each word is a valid dictionary
 *              word.
 * 
 *              Return all such possible sentences.
 * 
 *              For example, given s = "catsanddog", dict = ["cat", "cats",
 *              "and", "sand", "dog"].
 * 
 *              A solution is ["cats and dog", "cat sand dog"].
 */
public class WordBreakII {

	// dfs + memorized
	public ArrayList<String> wordBreak(String s, Set<String> dict) {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (String str : dict) {
			min = Math.min(min, str.length());
			max = Math.max(max, str.length());
		}
		Map<String, ArrayList<String>> memorized = new HashMap<>();
		return wordBreakHelper(s, dict, min, max, memorized);
	}
	
	private ArrayList<String> wordBreakHelper(String s, Set<String> dict, int min, int max, Map<String, ArrayList<String>> memorized) {
		if (memorized.containsKey(s))
			return memorized.get(s);
		ArrayList<String> res = new ArrayList<>();
		if (s == null || s.length() == 0)
			return res;
		if (dict.contains(s))
			res.add(s);
		// pruning
		for (int i = min; i <= Math.min(s.length(), max); i++) {
			String prefix = s.substring(0, i);
			if (dict.contains(prefix)) {
				String suffix = s.substring(i);
				List<String> temp = wordBreakHelper(suffix, dict, min, max, memorized);
				if (!temp.isEmpty()) {
					for (String str : temp)
						res.add(prefix + " " + str);
				}
			}
		}
		memorized.put(s, res);
		return res;
	}
	
	@Test
	public void testWordBreak() {
		String s = "catsanddog";
		Set<String> dict = new HashSet<>();
		dict.add("cat");
		dict.add("cats");
		dict.add("and");
		dict.add("sand");
		dict.add("dog");
		for (String str : wordBreak(s, dict)) {
			System.out.println(str);
		}
	}
	
	// DP + back track  
	public ArrayList<String> wordBreak2(String s, Set<String> dict) {  
	    int n = s.length();  
	    ArrayList<ArrayList<Integer>> guidance = new ArrayList<ArrayList<Integer>>(  
	            n);  
	    // initialize  
	    for (int i = 0; i < n; ++i)  
	    	guidance.add(new ArrayList<Integer>());  
	    // DP. guidance[i] stores position j where could insert space  
	    for (int i = 0; i < n; ++i) {  
	        for (int j = i + 1; j <= n; ++j) {  
	            String prefix = s.substring(i, j);  
	            if (dict.contains(prefix))  
	            	guidance.get(j - 1).add(i);  
	        }  
	    }  
	    return getPath(s, n - 1, guidance);  
	}  
	  
	public ArrayList<String> getPath(String s, int n, ArrayList<ArrayList<Integer>> guidance) {  
	    ArrayList<String> res = new ArrayList<String>();  
	    for (int i : guidance.get(n)) {
	    	if (i == 0) {
	    		res.add(s.substring(i, n + 1));
	    	} else {
	    		ArrayList<String> temp = getPath(s, i - 1, guidance);
	    		String suffix = s.substring(i, n + 1);
	    		for (String str : temp) {
	    			res.add(str + " " + suffix);
	    		}
	    	}
	    }

	    return res;  
	}  
	
	@Test
	public void testWordBreak2() {
		String s = "catsanddog";
		Set<String> dict = new HashSet<>();
		dict.add("cat");
		dict.add("cats");
		dict.add("and");
		dict.add("sand");
		dict.add("dog");
		for (String str : wordBreak2(s, dict)) {
			System.out.println(str);
		}
	}
	
}
